// 将一个大数组分成两个小数组，然后递归的对两个小数组进行排序
// 具体实现是先找一个基准元素，将数组分成左右两部分，左部分的元素都小于基准元素，右部分的元素都大于基准元素
// 然后对左右两部分的数组都进行递归的调用快速排序
// 快速排序是一个原地排序，不需要创建额外的数组空间

// 找基准，划分
// 递归

import { swap, testSort , measureSort} from "hy-algokit";


function quickSort(arr:number[]): number[]{
    partition(0,arr.length - 1);

    function partition(left:number ,right:number){
        // 递归结束条件（递归是必须要有结束条件的!!!）
        if(left >= right) return;
        //1.找到基准元素(轴心)
        // 添加三数取中,这样可以避免当我们每次选中的最后的一个数值都是最大值时，所导致的效率过低问题传递
        // const mid = left + Math.floor((left + right)/2);
        // if (arr[left] > arr[right]) swap(arr,left,right);
        // if(arr[mid] > arr[right]) swap(arr,mid,right);
        // if(arr[left] > arr[mid]) swap(arr,left,mid)
        // swap(arr,mid,right)
        const pivot = arr[right];

        //2.双指针进行交换操作（左边是比pivot小的数字，右边是比pivot大的数字）
        let i = left;
        let j = right - 1;
        
        while(i <= j){
            // 找到一个比pivot小的元素
            while(arr[i]<pivot){
                i++;
            }
            // 找到一个比pivot大的元素
            while(arr[j] > pivot){
                j--;
            }
            // 交换位置
            if(i <= j){
                swap(arr,i,j);
                i++;
                j--;
            }
        }
        // 将基础元素插入到i的位置,
        swap(arr,i,right);
        // 递归左边和右边
        partition(left,j);
        partition(i+1,right);
    }
    return arr;
}

testSort(quickSort);
measureSort(quickSort);



// 将一个大数组分成两个小数组，然后递归的对两个小数组进行排序
// 具体实现是先找一个基准元素，将数组分成左右两部分，左部分的元素都小于基准元素，右部分的元素都大于基准元素
// 然后对左右两部分的数组都进行递归的调用快速排序
// 快速排序是一个原地排序，不需要创建额外的数组空间

// 找基准，划分
// 递归

// import { swap, testSort , measureSort} from "hy-algokit";


// function quickSort(arr:number[]): number[]{
//     partition(0,arr.length - 1);

//     function partition(left:number ,right:number){
//         // 递归结束条件（递归是必须要有结束条件的!!!）
//         if(left >= right) return;
//         //1.找到基准元素(轴心)
//         const pivot = arr[right];

//         //2.双指针进行交换操作（左边是比pivot小的数字，右边是比pivot大的数字）
//         let i = left;
//         let j = right - 1;
        
//         while(i <= j){
//             // 找到一个比pivot小的元素
//             while(arr[i]<pivot){
//                 i++;
//             }
//             // 找到一个比pivot大的元素
//             while(arr[j] > pivot){
//                 j--;
//             }
//             // 交换位置
//             if(i <= j){
//                 swap(arr,i,j);
//                 i++;
//                 j--;
//             }
//         }
//         // 将基础元素插入到i的位置,
//         swap(arr,i,right);
//         // 递归左边和右边
//         partition(left,j);
//         partition(i+1,right);
//     }
//     return arr;
// }

// testSort(quickSort);
// measureSort(quickSort);